/**
 * ////编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。
 * ////
 * //// 待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
 * ////
 * //// 「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
 * ////
 * //// 请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。
 * ////
 * ////
 * ////
 * //// 示例：
 * ////
 * ////
 * ////输入：
 * ////image = [[1,1,1],[1,1,0],[1,0,1]]
 * ////sr = 1, sc = 1, newColor = 2
 * ////输出：[[2,2,2],[2,2,0],[2,0,1]]
 * ////解释:
 * ////初始坐标点位于图像的正中间，坐标 (sr,sc)=(1,1) 。
 * ////初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2 。
 * ////注意，右下角的像素没有更改为 2 ，因为它不属于初始坐标点的周围区域。
 * ////
 * ////
 * ////
 * ////
 * //// 提示：
 * ////
 * ////
 * //// image 和 image[0] 的长度均在范围 [1, 50] 内。
 * //// 初始坐标点 (sr,sc) 满足 0 <= sr < image.length 和 0 <= sc < image[0].length 。
 * //// image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535] 内。
 * ////
 * //// Related Topics 深度优先搜索 广度优先搜索 数组 矩阵 👍 50 👎 0
 * //
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

import java.util.ArrayDeque;
import java.util.Queue;

public class ID_interview_08_10_ColorFillLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_08_10_ColorFillLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
            //图像边界
            int rowNum = image.length;
            int colNum = image[0].length;
            image = BFS(image, sr, sc, newColor, rowNum, colNum);

            return image;
        }

        public int[][] BFS(int[][] image, int sr, int sc, int newColor, int rowNum, int colNum) {
            //是否遍历矩阵，空间复杂度O(M*N)
            boolean[][] visited = new boolean[rowNum][colNum];

            int startColor = image[sr][sc];

            Queue<int[]> pointQueue = new ArrayDeque<>();

            pointQueue.offer(new int[]{sr, sc});

            int[][] differ = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            while (pointQueue.peek() != null) {

                //检查点
                int[] nowPoint = pointQueue.poll();
                int x = nowPoint[0];
                int y = nowPoint[1];
                //如果检查过，就跳到下一个
                if (visited[x][y]) {
                    continue;
                }
                //颜色替换
                visited[x][y] = true;
                image[x][y] = newColor;
                //下上右左四个方向检索
                for (int i = 0; i < differ.length; i++) {
                    int adjX = x + differ[i][0];
                    int adjY = y + differ[i][1];
                    //重点来了,越界，或者检查过了，！！或者颜色不相等 ！！就跳过
                    if (adjX < 0 || adjX >= rowNum || adjY < 0 || adjY >= colNum //,越界，或者检查过了
                            || visited[adjX][adjY] // 检查过了
                            || image[adjX][adjY] != startColor //不等于默认颜色
                    ) {
                        continue;
                    }
                    //符合要求的点，添加到路径中
                    pointQueue.offer(new int[]{adjX, adjY});

                }


            }

            return image;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}